package GreedyAlgorithm;


/**
 * 在路上安装路灯，一个路灯照亮3格，求最少需要多少路灯把 . 代表的路点亮
 * examples: xx..xx..x......xx   -> 4个路灯
 * x...x...x  -> 2个路灯
 *
 * @author Liaorun
 */
public class Light {

    public static void main(String[] args) {
        System.out.println(minLight("x...x"));
    }

    public static int minLight(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        char[] str = s.toCharArray();

        int index = 0, light = 0;

        while (index < str.length) {
            if (str[index] == 'x') {
                // 当前位置是墙，不用管，看下一个位置
                index++;
            } else {
                light++;
                if (index + 1 == str.length) {
                    // 来到路的尽头
                    break;
                } else {
                    if (str[index + 1] == 'x') {
                        // 当前位置是路，且下一个位置是墙
                        // 把灯放到index位置，index 跳到墙后面 index + 2
                        index = index + 2;
                    } else {
                        // 当前位置是路，且下一个位置也是路
                        // 把灯放到index + 1位置，index 跳到 index + 3,
                        // 不用管index + 2 的位置，因为可以被照亮
                        index = index + 3;
                    }
                }
            }
        }

        return light;
    }
}
